<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  
  <meta name="description" content="分而治之的分析" />
  

  
  
  
  
  
  
  <title>MaxSubseqSum | 土木工程在读。。</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="分而治之的分析">
<meta property="og:type" content="article">
<meta property="og:title" content="MaxSubseqSum">
<meta property="og:url" content="https://civilprogrammer.gitee.io/2020/04/15/MaxSubseqSum/index.html">
<meta property="og:site_name" content="土木工程在读。。">
<meta property="og:description" content="分而治之的分析">
<meta property="og:locale" content="en_US">
<meta property="article:published_time" content="2020-04-14T16:31:52.000Z">
<meta property="article:modified_time" content="2020-05-17T08:00:12.000Z">
<meta property="article:author" content="CivilProgrammer">
<meta name="twitter:card" content="summary">
  
  
    <link rel="icon" href="/CivilProgrammer/css/images/favicon.ico">
  
  
<link rel="stylesheet" href="/CivilProgrammer/css/style.css">

  

  
  <!-- baidu webmaster push -->
  <script src='//push.zhanzhang.baidu.com/push.js'></script>
<meta name="generator" content="Hexo 5.0.0"></head>
<body class="home blog custom-background custom-font-enabled single-author">
  <div id="page" class="hfeed site">
      <header id="masthead" class="site-header" role="banner">
    <hgroup>
      <h1 class="site-title">
        <a href="/CivilProgrammer/" title="土木工程在读。。" rel="home">土木工程在读。。</a>
      </h1>
      
        <h2 class="site-description hitokoto"></h2>
        <script type="text/javascript" src="https://v1.hitokoto.cn/?encode=js"></script>
      
    </hgroup>

    <nav id="site-navigation" class="main-navigation" role="navigation">
            <button class="menu-toggle">菜单</button>
            <a class="assistive-text" href="/#content" title="跳至内容">跳至内容</a><!--TODO-->
            <div class="menu-main-container">
                <ul id="menu-main" class="nav-menu">
                
                    <li class="menu-item menu-item-type-post_type menu-item-object-page"><a href="/CivilProgrammer/">Home</a></li>
                
                    <li class="menu-item menu-item-type-post_type menu-item-object-page"><a href="/CivilProgrammer/archives">Archives</a></li>
                
                </ul>
            </div>
    </nav>
</header>

      <div id="main" class="wrapper">
        <div id="primary" class="site-content"><div id="content" role="main"><article id="post-MaxSubseqSum" class="post-MaxSubseqSum post type-post status-publish format-standard hentry">
    <!---->

      <header class="entry-header">
        
        
  
    <h1 class="entry-title article-title">
      MaxSubseqSum
    </h1>
  

        
        <div class="comments-link">
            
            <a href="javascript:void(0);" data-url="https://civilprogrammer.gitee.io/2020/04/15/MaxSubseqSum/" data-id="ckl9naii60007n8vldhl1e0kw" class="leave-reply bdsharebuttonbox" data-cmd="more">Share</a>
        </div><!-- .comments-link -->
      </header><!-- .entry-header -->

    <div class="entry-content">
      
        <h2 id="分而治之的分析"><a href="#分而治之的分析" class="headerlink" title="分而治之的分析"></a>分而治之的分析</h2><a id="more"></a> 
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">Max3</span><span class="params">( <span class="keyword">int</span> A, <span class="keyword">int</span> B, <span class="keyword">int</span> C )</span></span></span><br><span class="line"><span class="function"></span>&#123; <span class="comment">/* 返回3个整数中的最大值 */</span></span><br><span class="line">    <span class="keyword">return</span> A &gt; B ? A &gt; C ? A : C : B &gt; C ? B : C;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">DivideAndConquer</span><span class="params">( <span class="keyword">int</span> List[], <span class="keyword">int</span> left, <span class="keyword">int</span> right )</span></span></span><br><span class="line"><span class="function"></span>&#123; <span class="comment">/* 分治法求List[left]到List[right]的最大子列和 */</span></span><br><span class="line">    <span class="keyword">int</span> MaxLeftSum, MaxRightSum; <span class="comment">/* 存放左右子问题的解 */</span></span><br><span class="line">    <span class="keyword">int</span> MaxLeftBorderSum, MaxRightBorderSum; <span class="comment">/*存放跨分界线的结果*/</span></span><br><span class="line"> </span><br><span class="line">    <span class="keyword">int</span> LeftBorderSum, RightBorderSum;</span><br><span class="line">    <span class="keyword">int</span> center, i;</span><br><span class="line"> </span><br><span class="line">    <span class="keyword">if</span>( left == right )  &#123; <span class="comment">/* 递归的终止条件，子列只有1个数字 */</span></span><br><span class="line">        <span class="keyword">if</span>( List[left] &gt; <span class="number">0</span> )  <span class="keyword">return</span> List[left];</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"> </span><br><span class="line">    <span class="comment">/* 下面是&quot;分&quot;的过程 */</span></span><br><span class="line">    center = ( left + right ) / <span class="number">2</span>; <span class="comment">/* 找到中分点 */</span></span><br><span class="line">    <span class="comment">/* 递归求得两边子列的最大和 */</span></span><br><span class="line">    MaxLeftSum = DivideAndConquer( List, left, center );</span><br><span class="line">    MaxRightSum = DivideAndConquer( List, center+<span class="number">1</span>, right );</span><br><span class="line"> </span><br><span class="line">    <span class="comment">/* 下面求跨分界线的最大子列和 */</span></span><br><span class="line">    MaxLeftBorderSum = <span class="number">0</span>; LeftBorderSum = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>( i=center; i&gt;=left; i-- ) &#123; <span class="comment">/* 从中线向左扫描 */</span></span><br><span class="line">        LeftBorderSum += List[i];</span><br><span class="line">        <span class="keyword">if</span>( LeftBorderSum &gt; MaxLeftBorderSum )</span><br><span class="line">            MaxLeftBorderSum = LeftBorderSum;</span><br><span class="line">    &#125; <span class="comment">/* 左边扫描结束 */</span></span><br><span class="line"> </span><br><span class="line">    MaxRightBorderSum = <span class="number">0</span>; RightBorderSum = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>( i=center+<span class="number">1</span>; i&lt;=right; i++ ) &#123; <span class="comment">/* 从中线向右扫描 */</span></span><br><span class="line">        RightBorderSum += List[i];</span><br><span class="line">        <span class="keyword">if</span>( RightBorderSum &gt; MaxRightBorderSum )</span><br><span class="line">            MaxRightBorderSum = RightBorderSum;</span><br><span class="line">    &#125; <span class="comment">/* 右边扫描结束 */</span></span><br><span class="line"> </span><br><span class="line">    <span class="comment">/* 下面返回&quot;治&quot;的结果 */</span></span><br><span class="line">    <span class="keyword">return</span> Max3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum );</span><br><span class="line">&#125;</span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">MaxSubseqSum3</span><span class="params">( <span class="keyword">int</span> List[], <span class="keyword">int</span> N )</span></span></span><br><span class="line"><span class="function"></span>&#123; <span class="comment">/* 保持与前2种算法相同的函数接口 */</span></span><br><span class="line">    <span class="keyword">return</span> DivideAndConquer( List, <span class="number">0</span>, N<span class="number">-1</span> );</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="具体的四种算法-N-3-N-2-NlogN-N"><a href="#具体的四种算法-N-3-N-2-NlogN-N" class="headerlink" title="具体的四种算法(N^3 N^2 NlogN N)"></a>具体的四种算法(N^3 N^2 NlogN N)</h2><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 01-复杂度1 最大子列和问题 (20分)</span></span><br><span class="line"><span class="comment">// 给定K个整数组成的序列</span></span><br><span class="line"><span class="comment">// “最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列&#123; -2, 11, -4, 13, -5, -2 &#125;，其连续子列&#123; 11, -4, 13 &#125;有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// 本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// 数据1：与样例等价，测试基本正确性；</span></span><br><span class="line"><span class="comment">// 数据2：102个随机整数；</span></span><br><span class="line"><span class="comment">// 数据3：103个随机整数；</span></span><br><span class="line"><span class="comment">// 数据4：104个随机整数；</span></span><br><span class="line"><span class="comment">// 数据5：105个随机整数；</span></span><br><span class="line"><span class="comment">// 输入格式:</span></span><br><span class="line"><span class="comment">// 输入第1行给出正整数K (≤100000)；第2行给出K个整数，其间以空格分隔。</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// 输出格式:</span></span><br><span class="line"><span class="comment">// 在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// 输入样例:</span></span><br><span class="line"><span class="comment">// 6</span></span><br><span class="line"><span class="comment">// -2 11 -4 13 -5 -2</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// 输出样例:</span></span><br><span class="line"><span class="comment">// 20</span></span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAXN 100000</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">long</span> <span class="keyword">long</span> <span class="title">MaxSum</span><span class="params">(<span class="keyword">int</span> * a, <span class="keyword">int</span> length)</span></span>; <span class="comment">// 我写的垃圾代码</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">MaxSubSeqSum1</span><span class="params">(<span class="keyword">int</span> <span class="built_in">list</span>[], <span class="keyword">int</span> n)</span></span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">MaxSubseqSum2</span><span class="params">(<span class="keyword">int</span> <span class="built_in">list</span>[], <span class="keyword">int</span> n)</span></span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">MaxSubseqSum3</span><span class="params">(<span class="keyword">int</span> <span class="built_in">list</span>[], <span class="keyword">int</span> n)</span></span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">MaxSubseqSum4</span><span class="params">(<span class="keyword">int</span> <span class="built_in">list</span>[], <span class="keyword">int</span> n)</span></span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">DivideAndConquer</span><span class="params">(<span class="keyword">int</span> <span class="built_in">list</span>[], <span class="keyword">int</span> left, <span class="keyword">int</span> right)</span></span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">Max3</span><span class="params">(<span class="keyword">int</span> a, <span class="keyword">int</span> b, <span class="keyword">int</span> c)</span></span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> k, arr[MAXN] = &#123;<span class="number">0</span>&#125;;</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;k);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; k; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;arr[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;%d&quot;</span>, MaxSubseqSum4(arr, k));</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">MaxSubseqSum4</span><span class="params">(<span class="keyword">int</span> <span class="built_in">list</span>[], <span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> ThisSum = <span class="number">0</span>, MaxSum = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        ThisSum += <span class="built_in">list</span>[i];</span><br><span class="line">        <span class="keyword">if</span> (ThisSum &gt; MaxSum)</span><br><span class="line">        &#123;</span><br><span class="line">            MaxSum = ThisSum;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (ThisSum &lt; <span class="number">0</span>)</span><br><span class="line">        &#123;</span><br><span class="line">            ThisSum = <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> MaxSum;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">Max3</span><span class="params">(<span class="keyword">int</span> a, <span class="keyword">int</span> b, <span class="keyword">int</span> c)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> c &gt; (a &gt; b ? a : b) ? c : (a &gt; b ? a : b);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">DivideAndConquer</span><span class="params">(<span class="keyword">int</span> <span class="built_in">list</span>[], <span class="keyword">int</span> left, <span class="keyword">int</span> right)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> MaxRightSum, MaxLeftSum;</span><br><span class="line">    <span class="keyword">int</span> MaxLeftBorderSum, MaxRightBorderSum, LeftBorderSum, RightBorderSum;</span><br><span class="line">    <span class="keyword">int</span> center = (left + right) / <span class="number">2</span>;</span><br><span class="line">    <span class="keyword">if</span> (left == right)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">list</span>[left] &gt; <span class="number">0</span> ? <span class="built_in">list</span>[left] : <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        MaxLeftSum = DivideAndConquer(<span class="built_in">list</span>, left, center);</span><br><span class="line">        MaxRightSum = DivideAndConquer(<span class="built_in">list</span>, center + <span class="number">1</span>, right);</span><br><span class="line"></span><br><span class="line">        MaxLeftBorderSum = LeftBorderSum = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = center; i &gt;= left; i--)</span><br><span class="line">        &#123;</span><br><span class="line">            LeftBorderSum += <span class="built_in">list</span>[i];</span><br><span class="line">            <span class="keyword">if</span> (MaxLeftBorderSum &lt; LeftBorderSum)</span><br><span class="line">            &#123;</span><br><span class="line">                MaxLeftBorderSum = LeftBorderSum;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        MaxRightBorderSum = RightBorderSum = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = center + <span class="number">1</span>; i &lt;= right; i++)</span><br><span class="line">        &#123;</span><br><span class="line">            RightBorderSum += <span class="built_in">list</span>[i];</span><br><span class="line">            <span class="keyword">if</span> (MaxRightBorderSum &lt; RightBorderSum)</span><br><span class="line">            &#123;</span><br><span class="line">                MaxRightBorderSum = RightBorderSum;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> Max3(MaxLeftBorderSum + MaxRightBorderSum, MaxLeftSum, MaxRightSum);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">MaxSubseqSum3</span><span class="params">(<span class="keyword">int</span> <span class="built_in">list</span>[], <span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> DivideAndConquer(<span class="built_in">list</span>, <span class="number">0</span>, n - <span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">MaxSubseqSum2</span><span class="params">(<span class="keyword">int</span> <span class="built_in">list</span>[], <span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> ThisSum, MaxSum = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        ThisSum = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = i; j &lt; n; j++)</span><br><span class="line">        &#123;</span><br><span class="line">            ThisSum += <span class="built_in">list</span>[j];</span><br><span class="line">            <span class="keyword">if</span> (ThisSum &gt; MaxSum)</span><br><span class="line">            &#123;</span><br><span class="line">                MaxSum = ThisSum;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> MaxSum;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">MaxSubSeqSum1</span><span class="params">(<span class="keyword">int</span> <span class="built_in">list</span>[], <span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> ThisSum = <span class="number">0</span>, MaxSum = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = i; j &lt; n; j++)</span><br><span class="line">        &#123;</span><br><span class="line">            ThisSum = <span class="number">0</span>;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> k = i; k &lt; j + <span class="number">1</span>; k++)</span><br><span class="line">            &#123;</span><br><span class="line">                ThisSum += <span class="built_in">list</span>[k];</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (ThisSum &gt; MaxSum)</span><br><span class="line">            &#123;</span><br><span class="line">                MaxSum = ThisSum;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> MaxSum;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// long long MaxSum(int * arr, int length)</span></span><br><span class="line"><span class="comment">// &#123;</span></span><br><span class="line"><span class="comment">//     long long ret, lsum, rsum, temp_lsum, temp_rsum, tsum, MaxLeftBorderSum, MaxRightBorderSum;</span></span><br><span class="line"><span class="comment">//     MaxLeftBorderSum = MaxRightBorderSum = tsum = ret = lsum = rsum = temp_lsum = temp_rsum = 0;</span></span><br><span class="line"><span class="comment">//     // int * left = 0, * right = 0;</span></span><br><span class="line"><span class="comment">//     // left = (int *)malloc(length / 2 * sizeof(int));</span></span><br><span class="line"><span class="comment">//     // right = (int *)malloc( (length - length / 2) * sizeof(int) );</span></span><br><span class="line"><span class="comment">//     int left[length / 2];</span></span><br><span class="line"><span class="comment">//     int right[length - length / 2];</span></span><br><span class="line"><span class="comment">//     if (length == 1)</span></span><br><span class="line"><span class="comment">//     &#123;</span></span><br><span class="line"><span class="comment">//         return arr[0] &gt;= 0 ? arr[0] : 0;</span></span><br><span class="line"><span class="comment">//     &#125;</span></span><br><span class="line"><span class="comment">//     else</span></span><br><span class="line"><span class="comment">//     &#123;</span></span><br><span class="line"><span class="comment">//         for (int i = 0; i &lt; length / 2; i++)</span></span><br><span class="line"><span class="comment">//         &#123;</span></span><br><span class="line"><span class="comment">//             left[i] = arr[i];</span></span><br><span class="line"><span class="comment">//         &#125;</span></span><br><span class="line"><span class="comment">//         for (int i = 0; i &lt; length - length / 2; i++)</span></span><br><span class="line"><span class="comment">//         &#123;</span></span><br><span class="line"><span class="comment">//             right[i] = arr[length / 2 + i];</span></span><br><span class="line"><span class="comment">//         &#125;</span></span><br><span class="line"><span class="comment">//         lsum = MaxSum(left, sizeof(left) / sizeof(left[0]));</span></span><br><span class="line"><span class="comment">//         rsum = MaxSum(right, sizeof(right) / sizeof(right[0]));</span></span><br><span class="line"><span class="comment">//         ret =  lsum &gt; rsum ? lsum : rsum;</span></span><br><span class="line"></span><br><span class="line"><span class="comment">//         for (int i = 0; i &lt; length - length / 2; i++)</span></span><br><span class="line"><span class="comment">//         &#123;</span></span><br><span class="line"><span class="comment">//             temp_rsum += right[i];</span></span><br><span class="line"><span class="comment">//             if (temp_rsum &gt; MaxRightBorderSum)</span></span><br><span class="line"><span class="comment">//             &#123;</span></span><br><span class="line"><span class="comment">//                 MaxRightBorderSum = temp_rsum;</span></span><br><span class="line"><span class="comment">//             &#125;</span></span><br><span class="line"><span class="comment">//         &#125;</span></span><br><span class="line"><span class="comment">//         for (int i = length / 2 - 1; i &gt;= 0; i--)</span></span><br><span class="line"><span class="comment">//         &#123;</span></span><br><span class="line"><span class="comment">//             temp_lsum += left[i];</span></span><br><span class="line"><span class="comment">//             if (temp_lsum &gt; MaxLeftBorderSum)</span></span><br><span class="line"><span class="comment">//             &#123;</span></span><br><span class="line"><span class="comment">//                 MaxLeftBorderSum = temp_lsum;</span></span><br><span class="line"><span class="comment">//             &#125;</span></span><br><span class="line"><span class="comment">//         &#125;</span></span><br><span class="line"><span class="comment">//         tsum = MaxLeftBorderSum + MaxRightBorderSum;</span></span><br><span class="line"><span class="comment">//         ret = ret &gt; tsum ? ret : tsum;</span></span><br><span class="line"><span class="comment">//         return ret;</span></span><br><span class="line"><span class="comment">//     &#125;</span></span><br><span class="line"><span class="comment">// &#125;</span></span><br></pre></td></tr></table></figure>

      
    </div><!-- .entry-content -->

    <footer class="entry-meta">
    <a href="/CivilProgrammer/2020/04/15/MaxSubseqSum/">
    <time datetime="2020-04-14T16:31:52.000Z" class="entry-date">
        2020-04-15
    </time>
</a>
    
    
    </footer>
</article>


    
<nav class="nav-single">
    <h3 class="assistive-text">文章导航</h3>
    
        <span class="nav-previous"><a href="/CivilProgrammer/2020/04/20/%E6%8E%A5%E4%B8%8B%E6%9D%A5%E7%9A%84%E8%AE%A1%E7%AE%97%E6%9C%BA%E5%AD%A6%E4%B9%A0%E4%B9%8B%E8%B7%AF/" rel="prev"><span class="meta-nav">←</span> 接下来的计算机学习之路</a></span>
    
    
        <span class="nav-next"><a href="/CivilProgrammer/2020/04/14/JosephusProblem/" rel="next">JosephusProblem <span class="meta-nav">→</span></a></span>
    
</nav><!-- .nav-single -->







</div></div>
        <div id="secondary" class="widget-area" role="complementary">
  
    <aside id="search" class="widget widget_search"><form role="search" method="get" accept-charset="utf-8" id="searchform" class="searchform" action="//google.com/search">
    <div>
        <input type="text" value="" name="s" id="s" />
        <input type="submit" id="searchsubmit" value="搜索" />
    </div>
</form></aside>
  
    
  
    
  
    
  <aside class="widget">
    <h3 class="widget-title">Recents</h3>
    <div class="widget-content">
      <ul>
        
          <li>
            <a href="/CivilProgrammer/2021/02/18/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E6%9F%A5%E6%89%BE%E7%AB%A0%E8%8A%82%E4%B9%A0%E9%A2%98%E5%88%B7%E5%AE%8C/">数据结构查找章节习题刷完</a>
          </li>
        
          <li>
            <a href="/CivilProgrammer/2021/02/13/vmware%E4%B8%ADcentos7%E4%B8%8BNAT%E6%A8%A1%E5%BC%8F%E8%AE%BE%E7%BD%AE%E9%9D%99%E6%80%81ip/">vmware中centos7下NAT模式设置静态ip</a>
          </li>
        
          <li>
            <a href="/CivilProgrammer/2020/12/31/2020-12-31/">2020-12-31</a>
          </li>
        
          <li>
            <a href="/CivilProgrammer/2020/12/06/VSCode%E4%B8%AD%E6%96%87%E8%BE%93%E5%87%BA%E4%B9%B1%E7%A0%81/">VSCode中文输出乱码</a>
          </li>
        
          <li>
            <a href="/CivilProgrammer/2020/10/10/%E5%BB%BA%E5%B7%A5%E7%B2%BE%E7%A5%9E%E4%BC%A0%E6%89%BF%E8%80%85%E8%AF%84%E9%80%89%E2%80%94%E2%80%94%E5%8B%A4%E5%A5%8B%E5%A5%BD%E5%AD%A6/">(no title)</a>
          </li>
        
      </ul>
    </div>
  </aside>

  
    
  
    
  
</div>
      </div>
      <footer id="colophon" role="contentinfo">
    <p>&copy; 2021 CivilProgrammer
    All rights reserved.</p>
    <p>Powered by <a href="http://hexo.io/" target="_blank">Hexo</a></p>
</footer>
    <script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"1","bdMiniList":false,"bdPic":"","bdStyle":"2","bdSize":"16"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='/js/share.js'];</script>

<script src="/js/jquery-3.3.1.min.js"></script>


  
<link rel="stylesheet" href="/CivilProgrammer/fancybox/jquery.fancybox.css">

  
<script src="/CivilProgrammer/fancybox/jquery.fancybox.pack.js"></script>




<script src="/CivilProgrammer/js/script.js"></script>


<script src="/js/navigation.js"></script>

<div id="bg"></div>

  </div>
</body>
</html>